﻿// --------------------------------------------------------------------------------------------------------------------
// <copyright file="TabuSearch.cs" company="Luis de la Torre">
//   Copyright Luis de la Torre, unless otherwise indicated
// </copyright>
// <summary>
//   The tabu search.
// </summary>
// --------------------------------------------------------------------------------------------------------------------
namespace PVRP_SR
{
    using System.Collections.Generic;
    using System.Diagnostics;
    using System.Linq;

    /// <summary>
    /// The tabu search.
    /// </summary>
    public class TabuSearch : ImprovementHeuristic
    {
        #region Fields

        /// <summary>
        /// The diversification intensity.
        /// </summary>
        private readonly int diversificationIntensity;

        /// <summary>
        /// The geni insertion.
        /// </summary>
        private readonly Geni geni;

        /// <summary>
        /// The infeasibility penalty.
        /// </summary>
        private readonly double infeasibilityPenalty;

        /// <summary>
        /// The number of nearest neighbors.
        /// </summary>
        private readonly int numNearestNeighbors;

        /// <summary>
        /// The number of nearest neighbors for moves.
        /// </summary>
        private readonly int numNearestNeighborsForMoves;

        /// <summary>
        /// The _solution attributes.
        /// </summary>
        private readonly HashSet<TabuAttribute> solutionAttributes;

        /// <summary>
        /// The tabu limit.
        /// </summary>
        private readonly int tabuLimit;

        /// <summary>
        /// The iteration.
        /// </summary>
        private int iteration;

        /// <summary>
        /// The move evaluator.
        /// </summary>
        private MoveEvaluator<PvrpSrMove> moveEvaluator;

        #endregion

        #region Constructors and Destructors

        /// <summary>
        /// Initializes a new instance of the <see cref="TabuSearch"/> class. 
        /// Initialize a tabu search with an initial (possibly infeasible) solution.
        /// </summary>
        /// <param name="solution">
        /// Initial solution
        /// </param>
        /// <param name="tabuLimit">
        /// Fixed-length tabu parameter
        /// </param>
        /// <param name="diversificationIntensity">
        /// Diversification intensity parameter
        /// </param>
        /// <param name="infeasibilityPenalty">
        /// The infeasibility Penalty.
        /// </param>
        /// <param name="numNearestNeighbors">
        /// Number of nearest neighbors to consider when moving between solutions
        /// </param>
        /// <param name="numNearestNeighborsForMoves">
        /// The number of nearest neighbors for moves.
        /// </param>
        public TabuSearch(
            PvrpSrSolution solution, 
            int tabuLimit, 
            int diversificationIntensity, 
            double infeasibilityPenalty, 
            int numNearestNeighbors, 
            int numNearestNeighborsForMoves)
        {
            this.geni = new Geni(solution, numNearestNeighbors);
            this.tabuLimit = tabuLimit;
            this.diversificationIntensity = diversificationIntensity;
            this.infeasibilityPenalty = infeasibilityPenalty;
            this.solutionAttributes = new HashSet<TabuAttribute>();
            this.numNearestNeighbors = numNearestNeighbors;
            this.numNearestNeighborsForMoves = numNearestNeighborsForMoves;
            this.iteration = 0;
            const int NumIterationsIncluded = 1;
            Geni x = new Geni(solution, this.numNearestNeighbors);

            // add all of the attributes of the initial solution
            for (int t = 0; t < solution.Instance.NumDays; t++)
            {
                for (int k = 0; k < solution.Instance.NumVehicles; k++)
                {
                    foreach (
                        int node in solution.Routes[t, k].Nodes.Where(node => node != solution.Instance.StartDepots[0]))
                    {
                        this.solutionAttributes.Add(new TabuAttribute(k, node, this.iteration, NumIterationsIncluded));
                    }
                }
            }
        }

        #endregion

        #region Public Methods and Operators

        /// <summary>
        /// Run tabu search and return an improved solution
        /// </summary>
        /// <param name="solution">
        /// The solution
        /// </param>
        public override void ImproveSolution(PvrpSrSolution solution)
        {
            this.iteration = 0;
            List<PvrpSrMove> moves = this.ReturnMoves(solution);
            this.geni.Moves = moves;
            this.geni.ImproveSolution(solution);
        }

        #endregion

        #region Methods

        /// <summary>
        /// Construct moves and return a set of them
        /// There are numVehicles-1 potential driver moves for a
        /// customer on each day service is requested.
        /// Drivers containing one of the customer's numNearestNeighborsForMoves
        /// nearest neighbors are considered as a possible move destination for moves
        /// </summary>
        /// <param name="solution">
        /// The solution.
        /// </param>
        /// <returns>
        /// The <see cref="List"/>.
        /// </returns>
        private List<PvrpSrMove> ReturnMoves(PvrpSrSolution solution)
        {
            List<PvrpSrMove> moves = new List<PvrpSrMove>();
            for (int i = 0; i < solution.Instance.NumNodesRegular; i++)
            {
#if DEBUG
                for (int t = 0; t < solution.Instance.NumDays; t++)
                {
                    if (!(solution.Instance.Demands[t][i] >= 0))
                    {
                        continue;
                    }

                    if (!solution.IsRouted(t, i))
                    {
                        solution.PrintSolution();
                    }

                    Debug.Assert(
                        solution.IsRouted(t, i), 
                        "this function assumes that all customers that have demand on day t are routed");
                }

#endif
                for (int k = 0; k < solution.Instance.NumVehicles; k++)
                {
                    // find the first day that the node demands service
                    int t;
                    for (t = 0; t < solution.Instance.NumDays; t++)
                    {
                        if (solution.Instance.Demands[t][i] >= 0)
                        {
                            break;
                        }
                    }

                    // move must consistent of actually moving to another vehicle
                    // if route k contains node i on day t, it contains node i on every day that i demands service
                    if (solution.Routes[t, k].Nodes.Contains(i))
                    {
                        continue;
                    }

                    // check if the driver's route contains one of the nearest neighbors of i
                    // true if the driver's route contains one of the nearest neighbors on any day
                    bool routeContainsNeighbor = false;
                    for (t = 0; t < solution.Instance.NumDays; t++)
                    {
                        // skip the node itself, which is geni.NeighborsSorted[i][0]
                        for (int j = 1; j < this.numNearestNeighborsForMoves; j++)
                        {
                            if (!solution.Routes[t, k].Nodes.Contains(this.geni.NeighborsSorted[i][j]))
                            {
                                continue;
                            }

                            routeContainsNeighbor = true;
                            break;
                        }

                        if (routeContainsNeighbor)
                        {
                            break;
                        }
                    }

                    if (routeContainsNeighbor)
                    {
                        moves.Add(new PvrpSrMove(i, k));
                    }
                }
            }

            return moves;
        }

        #endregion
    }
}